package com.yangli.leecode.mashib.interview;

/**
 * @Description
 * @Author liyang
 * @Date 2023/2/17 11:34
 */
public class TwentyOne {
    public static void main(String[] args){
        TwentyOne twentyOne = new TwentyOne();

        System.out.println(twentyOne.solution(10, 17, 21));
        System.out.println(twentyOne.solution2(10, 17, 21));

    }


    public double solution(int N, int a, int b){
        if (N < 1 || a >= b || a < 0) {//边界
            return 0;
        }
        if (b - a >= N) {
            return 1;
        }
        return f1(0, N, a, b);
    }

    //暴力递归
    public double f1(int cur, int N, int a, int b){
        if (cur >= a && cur < b) {//当前累加和为cur，赢的概率
            return 1;
        }
        if (cur >= b) {
            return 0;
        }
        double win = 0.0;
        for (int i = 1; i <= N; i++) {//全可能遍历
            win += f1(cur + i, N, a, b);
        }
        return win / N;
    }


    //枚举优化
    public double f2(int cur, int N, int a, int b){
        if (cur >= a && cur < b) {//当前累加和为cur，赢的概率
            return 1;
        }
        if (cur >= b) {
            return 0;
        }
        if (cur == a - 1) {
            return (b - a) * 1.0 / N;
        }
        //f(n) = (f(n+1)+f(n+1)*N-f(n+1+N))/N ==>减少枚举
        double win = f2(cur + 1, N, a, b) + f2(cur + 1, N, a, b) * N;
        if (b < cur + 1 + N) {
            win -= f2(cur + 1 + N, N, a, b);
        }
        return win / N;
    }

    //动态规划
    public double solution2(int N, int a, int b){
        if (N < 1 || a >= b || a < 0) {//边界
            return 0;
        }
        if (b - a >= N) {
            return 1;
        }
        double[] dp = new double[b + 1];
        dp[b] = 0;
        for (int i = b - 1; i >= 0; i--) {
            if (i >= a) {
                dp[i] = 1.0;
                continue;
            }
            if (i == a - 1) {
                dp[i] = (b - a) * 1.0 / N;
                continue;
            }
            dp[i] = dp[i + 1] + dp[i + 1] * N;
            if (i + 1 + N < b) {
                dp[i] -= dp[i + 1 + N];
            }
            dp[i] = dp[i] / N;
        }
        return dp[0];
    }


}
